#pragma once

#include <iostream>
#include <vector>
using namespace std;

template<class T>
struct HashNode
{
	T _data;
	HashNode* _next; // 不用存状态栏了，存下一个结点指针

	HashNode(const T& data)
		:_data(data)
		, _next(nullptr)
	{}
};

template<class K>
struct HashFunc // 可以把闭散列的HashFunc放在外面直接用，但是这就不放了
{
	size_t operator()(const K& key)
	{
		return (size_t)key; // 负数，浮点数，指针等可以直接转，string不行
	}
};

template<>
struct HashFunc<string> // 上面的特化
{
	size_t operator()(const string& key)
	{
		size_t val = 0;
		for (const auto& ch : key)
		{
			val *= 131;
			val += ch;
		}

		return val;
	}
};

template<class K, class T, class Hash, class KeyOfT>
class HashTable; // 前置声明

template<class K, class T, class Hash, class KeyOfT>
class __HashIterator
{
public:
	typedef HashNode<T> Node;
	typedef HashTable<K, T, Hash, KeyOfT> HT;
	typedef __HashIterator<K, T, Hash, KeyOfT> Self;

	Node* _node; // 数据结点
	HT* _pht; // 哈希表指针

	__HashIterator(Node* node, HT* pht)
		:_node(node)
		, _pht(pht)
	{}

	Self& operator++()
	{
		if (_node->_next) // 不是桶中的最后一个数据
		{
			_node = _node->_next;
		}
		else // 是桶中的最后一个数据，找下一个桶
		{
			Hash hs;
			KeyOfT kot;
			size_t i = hs(kot(_node->_data)) % _pht->_tables.size() + 1;//没+1是当前桶位置
			for (; i < _pht->_tables.size(); ++i)
			{
				if (_pht->_tables[i]) // 向后迭代找到了有桶的位置
				{
					_node = _pht->_tables[i]; // 把这个位置给_node
					break;
				}
			}
			if (i == _pht->_tables.size()) // 后面都没桶了
			{
				_node = nullptr;
			}
		}
		return *this; // this指向调用该函数的对象（迭代器），指向下一个后解引用返回
	}

	T& operator*()
	{
		return _node->_data;
	}

	T* operator->()
	{
		return &_node->_data;
	}

	bool operator!=(const Self& s) const
	{
		return s._node != _node;
	}

	bool operator==(const Self& s) const
	{
		return s._node == _node;
	}
};

template<class K, class T, class Hash, class KeyOfT>
class HashTable
{
public:
	template<class K, class T, class Hash, class KeyOfT>
	friend class __HashIterator;

	typedef HashNode<T> Node;
	typedef __HashIterator<K, T, Hash, KeyOfT> iterator;

	iterator begin()
	{
		for (size_t i = 0; i < _tables.size(); ++i)
		{
			if (_tables[i])
			{
				return iterator(_tables[i], this); // 构造：(Node * node, HT * pht)
			}
		}
		return end();
	}

	iterator end()
	{
		return iterator(nullptr, this);
	}

	~HashTable()
	{
		for (size_t i = 0; i < _tables.size(); ++i)
		{
			Node* cur = _tables[i];
			while (cur)
			{
				Node* next = cur->_next;
				delete cur;
				cur = next;
			}
			_tables[i] = nullptr;
		}
	}

	iterator Find(const K& key)
	{
		if (_tables.size() == 0)
		{
			return end();
		}

		Hash hs;
		KeyOfT kot;
		size_t hashi = hs(key) % _tables.size();
		Node* cur = _tables[hashi];
		while (cur)
		{
			if (kot(cur->_data) == key)
			{
				return iterator(cur,this);
			}
			cur = cur->_next;
		}
		return end();
	}

	inline size_t __stl_next_prime(size_t n)
	{
		static const size_t __stl_num_primes = 28;
		static const size_t __stl_prime_list[__stl_num_primes] =
		{
			53, 97, 193, 389, 769,
			1543, 3079, 6151, 12289, 24593,
			49157, 98317, 196613, 393241, 786433,
			1572869, 3145739, 6291469, 12582917, 25165843,
			50331653, 100663319, 201326611, 402653189, 805306457,
			1610612741, 3221225473, 4294967291
		};

		for (size_t i = 0; i < __stl_num_primes; ++i)
		{
			if (__stl_prime_list[i] > n)
			{
				return __stl_prime_list[i];
			}
		}

		return -1; // 不会走到这，随便返回一个值
	}

	pair<iterator, bool> Insert(const T& data)
	{
		KeyOfT kot;
		iterator ret = Find(kot(data));
		if (ret != end())
		{
			return make_pair(ret, false);
		}

		Hash hs;
		if (_size == _tables.size()) // 负载因子到1就扩容
		{
			//size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
			vector<Node*> newTables;
			//newTables.resize(newSize, nullptr);
			newTables.resize(__stl_next_prime(_tables.size()), nullptr); //取素数，前两注释改成这一条

			for (size_t i = 0; i < _tables.size(); ++i) // 旧表中节点移动映射新表
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;

					size_t hashi = hs(kot(cur->_data)) % newTables.size();
					cur->_next = newTables[hashi];
					newTables[hashi] = cur;

					cur = next;
				}

				_tables[i] = nullptr;
			}

			_tables.swap(newTables);
		}

		size_t hashi = hs(kot(data)) % _tables.size(); // 哈希映射
		Node* newnode = new Node(data); // 头插
		newnode->_next = _tables[hashi];
		_tables[hashi] = newnode;
		++_size;
		return make_pair(iterator(newnode, this), true);
	}

	bool Erase(const K& key)
	{
		if (_tables.size() == 0) // 防止除零错误
		{
			return false;
		}

		Hash hs;
		KeyOfT kot;
		size_t hashi = hs(key) % _tables.size();
		Node* cur = _tables[hashi];
		Node* prev = nullptr;
		while (cur)
		{
			if (kot(cur->_data) == key)
			{
				if (prev == nullptr) // 头插，先把指针数组存的指针指向cur的下一个
				{
					_tables[hashi] = cur->_next;
				}
				else // 中间删
				{
					prev->_next = cur->_next;
				}
				delete cur; // 统一在这delete
				return true;
			}

			prev = cur; // 往后走
			cur = cur->_next;
		}
		return false; // 没找到
	}

	size_t Size() // 存的数据个数
	{
		return _size;
	}

	size_t TablesSize() // 表的长度
	{
		return _tables.size();
	}

	size_t BucketNum() // 桶的个数
	{
		size_t num = 0;
		for (size_t i = 0; i < _tables.size(); ++i)
		{
			if (_tables[i]) // 如果不是空就有桶
			{
				++num;
			}
		}
		return num;
	}

	size_t MaxBucketLenth() // 最长桶的长度
	{
		size_t maxLen = 0;
		for (size_t i = 0; i < _tables.size(); ++i)
		{
			size_t len = 0;
			Node* cur = _tables[i];
			while (cur)
			{
				++len;
				cur = cur->_next;
			}
			if (len > maxLen)
			{
				maxLen = len;
			}
		}
		return maxLen;
	}

protected:
	vector<Node*> _tables; // 指针数组
	size_t _size;
};